/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package phd.dupenois.changeidentifiers.algorithms.chihull;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import uk.co.dupenois.geometry.Coordinate;

/**
 *
 * @author mpd209
 */
public class DivideAndConquerDelaunayTriangulation {

    private ArrayList<Coordinate> xSortedCoordinateList;
    private ArrayList<DelaunayTriangle> finishedTriangulation;

    public DivideAndConquerDelaunayTriangulation(
            ArrayList<Coordinate> xSortedCoordinateList) {
        this(xSortedCoordinateList, false);
    }

    public DivideAndConquerDelaunayTriangulation(
            ArrayList<Coordinate> coordinateList, boolean sort) {
        if (sort) {
            Collections.sort(coordinateList, Coordinate.MinXMinYComparator);
        }
        this.xSortedCoordinateList = coordinateList;
    }


    public ArrayList<DelaunayTriangle> triangulate(){
        this.finishedTriangulation = constructTriangulation(xSortedCoordinateList);
        return this.finishedTriangulation;
    }

    public ArrayList<DelaunayTriangle> constructTriangulation(ArrayList<Coordinate> list){
        ArrayList<DelaunayTriangle> triangulation;
        if(list.size()>3){
            ArrayList<ArrayList<Coordinate>> lists = split(list);
            ArrayList<Coordinate> left = lists.get(0);
            ArrayList<Coordinate> right = lists.get(1);
            ArrayList<DelaunayTriangle> triangulationLeft = constructTriangulation(left);
            ArrayList<DelaunayTriangle> triangulationRight = constructTriangulation(right);
            triangulation = mergeTriangulations(triangulationLeft, triangulationRight);
        }else{
            triangulation =  new ArrayList<DelaunayTriangle>();
            DelaunayTriangle triangle = null;
            if(list.size()==3){
                triangle = new DelaunayTriangle(list.get(0), list.get(1), list.get(2), true);
            }else if(list.size()==2){
                triangle = new DelaunayTriangle(list.get(0), list.get(1), true);
            }
            if(triangle!=null) triangulation.add(triangle);
        }
        return triangulation;
    }


    private ArrayList<ArrayList<Coordinate>> split(ArrayList<Coordinate> list){
        int size = list.size();
        int half = (int)Math.floor((double)size/2d);
        ArrayList<Coordinate> left = new ArrayList<Coordinate>();
        ArrayList<Coordinate> right = new ArrayList<Coordinate>();
        left.addAll(list.subList(0, half));
        right.addAll(list.subList(half, size));
        ArrayList<ArrayList<Coordinate>> result = new ArrayList<ArrayList<Coordinate>>();
        result.add(left);
        result.add(right);
        return result;
    }

    public ArrayList<DelaunayTriangle> mergeTriangulations(ArrayList<DelaunayTriangle> left,
            ArrayList<DelaunayTriangle> right){
        ArrayList<DelaunayTriangle> triangulation = new ArrayList<DelaunayTriangle>();
        //First find baseline

        return triangulation;
    }

}
